import java.util.HashMap;
import java.util.Map;

/**
 *给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 https://leetcode.cn/problems/palindrome-linked-list/description/*
 *思路：后序遍历
 */
class IsPalindromeDiGui {
    ListNode left = null;
    public boolean isPalindrome(ListNode head) {
        left = head;
        return travel(head);
    }

    private boolean travel(ListNode right) {
        if(right == null) {
            return true;
        }
        boolean res = travel(right.next);
        res = res & (right.val == left.val);
        left = left.next;
        return res;
    }
}